package 动态规划.递归参数思考型;

/**
 * 一种新的 动态规划的 思考方式
 * @author I adore you
 */
public class leetcode买卖股票的最佳时机121 {
	
	public static void main(String []args) {
//		int prices[] = {7,1,5,3,6,4};
		int prices[] = {5,4,3,2,1};
		System.out.println(violence(prices));
		System.out.println(greedy(prices));
		System.out.println(recursion(0,0,prices,prices.length));
	}
	
	
	
	// 暴力 写法  时间复杂度 O（N ^ 2）
	public  static int violence(int price[]) {
		int len =  price.length;
		if(len == 1)
			return 0;
		int ans = 0;
		for(int i = 0;i < len;i++) {
			for(int j = i + 1;j < len;j++) {
				ans = Math.max(ans, price[j] - price[i]);
			}
		}
		return ans;
	}
	
	
	/**
	 * 起初 ，就是按照 贪心的思想去写，贪心的策略 也没有错，但是贪心的 coding 写错了
	 * 主要 就是太 纠结于 index + 1 天 ，其实从 index 当天开始计算，是 最容易coding 的
	 * 这个题 很巧妙的 就是    数组的下标，就是   时间轴 
	 * O(N)
	 */
	public static int greedy(int prices[]) {
		int minest = Integer.MAX_VALUE;
		int ans = 0;
		for(int i = 0;i < prices.length;i++) {
			// 边 遍历 边 找 minest ，在遍历的过程顺便把结果给计算了。 这写的就很妙
			minest = Integer.min(minest, prices[i]);
			ans = Math.max(ans, prices[i] - minest);
		}
		return ans;
	}
	
	
	
	/**
	 * 暴力递归
	 * 可以超时了
	 * 至少证明了这个 暴力递归的思路是正确的！
	 */
	
	public static int recursion(int index,int status,int prices[],int len) {
		if(index == len)
			return 0;
		int ans = 0;
		int ans1 = 0;
		if(status == 0) {
			// 选择 不出手
			ans = recursion(index + 1,status,prices,len);
			// 选择 买入
			ans1  = recursion(index + 1,1,prices,len) - prices[index];
		}
		else {
			ans = recursion(index + 1,status,prices,len);
			ans1 = prices[index];
			
		}
		return Math.max(ans, ans1);
	}
	
	/**
	 * 这个表是怎么 填的， 还是画个图 ，看一下这个 依赖的关系的
	 * 这个 dp 填表的时候确实需要画图理解一下；
	 */
	public int dp(int prices[]) {
		int len = prices.length;
		int dp[][] = new int [len + 1][2];
		dp[len][0] = 0;
		dp[len][1] = 0;
		for(int index = len -1 ;index >= 0;index--) {
			dp[index][0] = Math.max(dp[index + 1][0], dp[index + 1][1] - prices[index]);
			dp[index][1] = Math.max(dp[index + 1][1], prices[index]);
		}
		return dp[0][0];
	}	
}
